<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            DP：数字三角形模型 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><style>mjx-container[jax="SVG"] {
  direction: ltr;
}

mjx-container[jax="SVG"] > svg {
  overflow: visible;
}

mjx-container[jax="SVG"][display="true"] {
  display: block;
  text-align: center;
  margin: 1em 0;
}

mjx-container[jax="SVG"][justify="left"] {
  text-align: left;
}

mjx-container[jax="SVG"][justify="right"] {
  text-align: right;
}

g[data-mml-node="merror"] > g {
  fill: red;
  stroke: red;
}

g[data-mml-node="merror"] > rect[data-background] {
  fill: yellow;
  stroke: none;
}

g[data-mml-node="mtable"] > line[data-line] {
  stroke-width: 70px;
  fill: none;
}

g[data-mml-node="mtable"] > rect[data-frame] {
  stroke-width: 70px;
  fill: none;
}

g[data-mml-node="mtable"] > .mjx-dashed {
  stroke-dasharray: 140;
}

g[data-mml-node="mtable"] > .mjx-dotted {
  stroke-linecap: round;
  stroke-dasharray: 0,140;
}

g[data-mml-node="mtable"] > svg {
  overflow: visible;
}

[jax="SVG"] mjx-tool {
  display: inline-block;
  position: relative;
  width: 0;
  height: 0;
}

[jax="SVG"] mjx-tool > mjx-tip {
  position: absolute;
  top: 0;
  left: 0;
}

mjx-tool > mjx-tip {
  display: inline-block;
  padding: .2em;
  border: 1px solid #888;
  font-size: 70%;
  background-color: #F8F8F8;
  color: black;
  box-shadow: 2px 2px 5px #AAAAAA;
}

g[data-mml-node="maction"][data-toggle] {
  cursor: pointer;
}

mjx-status {
  display: block;
  position: fixed;
  left: 1em;
  bottom: 1em;
  min-width: 25%;
  padding: .2em .4em;
  border: 1px solid #888;
  font-size: 90%;
  background-color: #F8F8F8;
  color: black;
}

foreignObject[data-mjx-xml] {
  font-family: initial;
  line-height: normal;
  overflow: visible;
}

.MathJax path {
  stroke-width: 3;
}

mjx-container[display="true"] {
  overflow: auto hidden;
}

mjx-container[display="true"] + br {
  display: none;
}
</style><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">DP：数字三角形模型</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2020-11-09 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>3.2k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>14 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <blockquote>
<p>现在打算写一些短点的文章了，LeetCode系列不会再append了，如果写lc题会单独开一篇文章，然后写题解</p>
</blockquote>
<h2 id="数字三角形模型"><a href="#数字三角形模型" class="headerlink" title="数字三角形模型"></a>数字三角形模型</h2><p><a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/#120-%E4%B8%89%E8%A7%92%E5%BD%A2%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E5%92%8C">120. 三角形最小路径和</a></p>
<p><a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/#64-%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E5%92%8C">64. 最小路径和</a></p>
<p><a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/#Path-sum-three-ways">Path sum: three ways</a></p>
<p>之前写过题解的就不重复写了，还有很多类似的题就不一一列举出来了，详见<a href="http://imlgw.top/2019/09/01/leetcode-dong-tai-gui-hua/">LeetCode动态规划</a></p>
<blockquote>
<p>后续如果还有类似的题会append进来</p>
</blockquote>
<h2 id="1027-方格取数"><a href="#1027-方格取数" class="headerlink" title="1027. 方格取数"></a><a class="link" target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/1029/">1027. 方格取数<i class="fas fa-external-link-alt"></i></a></h2><p>设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：</p>
<p><img lazyload="" src="/images/loading.svg" data-src="https://files.catbox.moe/hhonhx.png"></p>
<p>某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。</p>
<p>在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。</p>
<p>此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。</p>
<p><strong>输入格式</strong></p>
<p>第一行为一个整数N，表示 N×N 的方格图。</p>
<p>接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。</p>
<p>行和列编号从 1 开始。</p>
<p>一行“0 0 0”表示结束。</p>
<p><strong>输出格式</strong></p>
<p>输出一个整数，表示两条路径上取得的最大的和。</p>
<p><strong>数据范围</strong></p>
<p>N≤10</p>
<p><strong>输入样例：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="number">8</span></span><br><span class="line"><span class="number">2</span> <span class="number">3</span> <span class="number">13</span></span><br><span class="line"><span class="number">2</span> <span class="number">6</span> <span class="number">6</span></span><br><span class="line"><span class="number">3</span> <span class="number">5</span> <span class="number">7</span></span><br><span class="line"><span class="number">4</span> <span class="number">4</span> <span class="number">14</span></span><br><span class="line"><span class="number">5</span> <span class="number">2</span> <span class="number">21</span></span><br><span class="line"><span class="number">5</span> <span class="number">6</span> <span class="number">4</span></span><br><span class="line"><span class="number">6</span> <span class="number">3</span> <span class="number">15</span></span><br><span class="line"><span class="number">7</span> <span class="number">2</span> <span class="number">14</span></span><br><span class="line"><span class="number">0</span> <span class="number">0</span> <span class="number">0</span></span><br></pre></td></tr></table></figure>
<p><strong>输出样例：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="number">67</span></span><br></pre></td></tr></table></figure>
<p><strong>难度：</strong> 简单</p>
<p><strong>来源：</strong>《信息学奥赛一本通》 , NOIP2000提高组</p>
<h3 id="解法一"><a href="#解法一" class="headerlink" title="解法一"></a>解法一</h3><p>一开始确实没想出来，主要是看着范围好小，然后不确定复杂度，以为可以搜索的，看了y总讲解了一点，然后想过来了，自己写了一个N^4的解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//input output省略</span></span><br><span class="line"><span class="comment">//N^4 dp</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">slove</span><span class="params">(<span class="keyword">int</span>[][] w, <span class="keyword">int</span> N)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span>[][][][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[N+<span class="number">1</span>][N+<span class="number">1</span>][N+<span class="number">1</span>][N+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i1 = <span class="number">1</span>; i1 &lt;= N; i1++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j1 = <span class="number">1</span>; j1 &lt;= N; j1++) {</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i2 = <span class="number">1</span>; i2 &lt;= N; i2++) {</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j2 = <span class="number">1</span>; j2 &lt;= N; j2++) {</span><br><span class="line">                    <span class="keyword">int</span> temp = dp[i1][j1][i2][j2];</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1][i2-<span class="number">1</span>][j2]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1][i2][j2-<span class="number">1</span>]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1][j1-<span class="number">1</span>][i2-<span class="number">1</span>][j2]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1][j1-<span class="number">1</span>][i2][j2-<span class="number">1</span>]);</span><br><span class="line">                    dp[i1][j1][i2][j2] = temp + ((i1==i2&amp;&amp;j1==j2) ? w[i1-<span class="number">1</span>][j1-<span class="number">1</span>] : (w[i1-<span class="number">1</span>][j1-<span class="number">1</span>] + w[i2-<span class="number">1</span>][j2-<span class="number">1</span>])); </span><br><span class="line">                }</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> dp[N][N][N][N];</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>其实如果是只有一条路径就很简单，线性DP就行了，<code>dp[i][j] = Max(dp[i-1][j], dp[i][j-1])</code>，但是这题涉及到了两条路径，所以我们可以将状态定义为<code>dp[i1][j1][i2][j2]</code>，含义为从（1，1）到（i1，j1）,(i2，j2)这两个点的最大和，到每个点有两种走法，2*2一共4种子状态，取Max就行了</p>
<p>但是这里会有一个问题，某个点的val被取走之后就不能再被取了。也就是说，这两条路径可能会有交点，这种情况需要额外处理，而相交的情况实际上也就是<code>i1==i2 &amp;&amp; j1 == j2</code>的时候，这种情况交点的值就只能算一次</p>
<h3 id="解法二"><a href="#解法二" class="headerlink" title="解法二"></a>解法二</h3><p>y总讲的解法，优化了一维状态，N^3的解法，非常的巧妙，因为只能向下和向右走，所以从（1，1）到（N-1，N-1），走的总步数一定是<code>2*N</code>，那么我们就可以通过步数K计算出另一个坐标，从而省去一维状态</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//N^3优化，根据走的总步数计算另一个坐标位置</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">slove2</span><span class="params">(<span class="keyword">int</span>[][] w, <span class="keyword">int</span> N)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span>[][][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">2</span>*N+<span class="number">1</span>][N+<span class="number">1</span>][N+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">2</span>; k &lt;= <span class="number">2</span>*N; k++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i1 = <span class="number">1</span>; i1 &lt;= N; i1++) {</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i2 = <span class="number">1</span>; i2 &lt;= N; i2++) {</span><br><span class="line">                <span class="keyword">int</span> j1 = k-i1, j2 = k-i2;</span><br><span class="line">                <span class="keyword">if</span> (<span class="number">1</span> &lt;= j1 &amp;&amp; j1 &lt;= N &amp;&amp; <span class="number">1</span> &lt;= j2 &amp;&amp; j2 &lt;= N) {</span><br><span class="line">                    <span class="keyword">int</span> temp = dp[k][i1][i2]; </span><br><span class="line">                    temp = Math.max(temp, dp[k-<span class="number">1</span>][i1-<span class="number">1</span>][i2-<span class="number">1</span>]);</span><br><span class="line">                    temp = Math.max(temp, dp[k-<span class="number">1</span>][i1-<span class="number">1</span>][i2]);</span><br><span class="line">                    temp = Math.max(temp, dp[k-<span class="number">1</span>][i1][i2-<span class="number">1</span>]);</span><br><span class="line">                    temp = Math.max(temp, dp[k-<span class="number">1</span>][i1][i2]);</span><br><span class="line">                    dp[k][i1][i2] = temp + ((i1==i2&amp;&amp;j1==j2) ? w[i1-<span class="number">1</span>][j1-<span class="number">1</span>] : (w[i1-<span class="number">1</span>][j1-<span class="number">1</span>] + w[i2-<span class="number">1</span>][j2-<span class="number">1</span>]));     </span><br><span class="line">                }</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> dp[<span class="number">2</span>*N][N][N];</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="275-传纸条"><a href="#275-传纸条" class="headerlink" title="275. 传纸条"></a><a class="link" target="_blank" rel="noopener" href="https://www.acwing.com/problem/content/277/">275. 传纸条<i class="fas fa-external-link-alt"></i></a></h2><p>小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。</p>
<p>一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。</p>
<p>幸运的是，他们可以通过传纸条来进行交流。</p>
<p>纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。</p>
<p>从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 </p>
<p>在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。</p>
<p>班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。 </p>
<p>还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。</p>
<p>小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。</p>
<p>现在，请你帮助小渊和小轩找到这样的两条路径。</p>
<p><strong>输入格式</strong></p>
<p>第一行有2个用空格隔开的整数 m 和 n，表示学生矩阵有 m 行 n 列。</p>
<p>接下来的 m 行是一个 m∗n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度，每行的 n 个整数之间用空格隔开。</p>
<p><strong>输出格式</strong></p>
<p>输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。</p>
<p><strong>数据范围:</strong></p>
<p>1≤n,m≤50</p>
<p><strong>输入样例：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="number">3</span> <span class="number">3</span></span><br><span class="line"><span class="number">0</span> <span class="number">3</span> <span class="number">9</span></span><br><span class="line"><span class="number">2</span> <span class="number">8</span> <span class="number">5</span></span><br><span class="line"><span class="number">5</span> <span class="number">7</span> <span class="number">0</span></span><br></pre></td></tr></table></figure>
<p><strong>输出样例：</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="number">34</span></span><br></pre></td></tr></table></figure>
<h3 id="解法一-1"><a href="#解法一-1" class="headerlink" title="解法一"></a>解法一</h3><p>和上面一题一样，虽然题目说的是一个从左上向右下，一个是从右下到左上，但是实际上依然是要求两条路径连接左上到右下，使得和最大，所以实际上直接照搬上面的代码就ok了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//N^3</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">solve</span><span class="params">(<span class="keyword">int</span>[][] w, <span class="keyword">int</span> m, <span class="keyword">int</span> n)</span></span>{</span><br><span class="line">    <span class="keyword">int</span>[][][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[m+n+<span class="number">1</span>][m+<span class="number">1</span>][m+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">2</span>; k &lt;= m+n; k++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i1 = <span class="number">1</span>; i1 &lt;= m; i1++) {</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i2 = <span class="number">1</span>; i2 &lt;= m; i2++) {</span><br><span class="line">                <span class="keyword">int</span> j1 = k - i1, j2 = k - i2;</span><br><span class="line">                <span class="keyword">if</span> (j1 &lt; <span class="number">1</span> || j1 &gt; n || j2 &lt; <span class="number">1</span> || j2 &gt; n) <span class="keyword">continue</span>;</span><br><span class="line">                <span class="keyword">int</span> temp = dp[k][i1][i2]; </span><br><span class="line">                temp = Math.max(temp, dp[k-<span class="number">1</span>][i1-<span class="number">1</span>][i2]);</span><br><span class="line">                temp = Math.max(temp, dp[k-<span class="number">1</span>][i1][i2-<span class="number">1</span>]);</span><br><span class="line">                temp = Math.max(temp, dp[k-<span class="number">1</span>][i1][i2]);</span><br><span class="line">                temp = Math.max(temp, dp[k-<span class="number">1</span>][i1-<span class="number">1</span>][i2-<span class="number">1</span>]);</span><br><span class="line">                dp[k][i1][i2] = temp + (i1==i2 ? w[i1-<span class="number">1</span>][j1-<span class="number">1</span>] : (w[i1-<span class="number">1</span>][j1-<span class="number">1</span>] + w[i2-<span class="number">1</span>][j2-<span class="number">1</span>]));</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> dp[m+n][m][m];</span><br><span class="line">}</span><br></pre></td></tr></table></figure>

<h2 id="1463-摘樱桃-II"><a href="#1463-摘樱桃-II" class="headerlink" title="1463. 摘樱桃 II"></a><a class="link" target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/cherry-pickup-ii/">1463. 摘樱桃 II<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>困难</strong></p>
<p>给你一个 <code>rows x cols</code> 的矩阵 <code>grid</code> 来表示一块樱桃地。 <code>grid</code> 中每个格子的数字表示你能获得的樱桃数目。</p>
<p>你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 <code>(0,0)</code> 出发，机器人 2 从右上角格子 <code>(0, cols-1)</code> 出发。</p>
<p>请你按照如下规则，返回两个机器人能收集的最多樱桃数目：</p>
<ul>
<li>  从格子 <code>(i,j)</code> 出发，机器人可以移动到格子 <code>(i+1, j-1)</code>，<code>(i+1, j)</code> 或者 <code>(i+1, j+1)</code> 。</li>
<li>  当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。</li>
<li>  当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。</li>
<li>  两个机器人在任意时刻都不能移动到 <code>grid</code> 外面。</li>
<li>  两个机器人最后都要到达 <code>grid</code> 最底下一行。</li>
</ul>
<p>给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。</p>
<p>你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。</p>
<p>请你按照如下规则，返回两个机器人能收集的最多樱桃数目：</p>
<p><strong>示例 1：</strong></p>
<p><img lazyload="" src="/images/loading.svg" data-src="https://files.catbox.moe/da5rxh.png"></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：grid = [[<span class="number">3</span>,<span class="number">1</span>,<span class="number">1</span>],[<span class="number">2</span>,<span class="number">5</span>,<span class="number">1</span>],[<span class="number">1</span>,<span class="number">5</span>,<span class="number">5</span>],[<span class="number">2</span>,<span class="number">1</span>,<span class="number">1</span>]]</span><br><span class="line">输出：<span class="number">24</span></span><br><span class="line">解释：机器人 <span class="number">1</span> 和机器人 <span class="number">2</span> 的路径在上图中分别用绿色和蓝色表示。</span><br><span class="line">机器人 <span class="number">1</span> 摘的樱桃数目为 (<span class="number">3</span> + <span class="number">2</span> + <span class="number">5</span> + <span class="number">2</span>) = <span class="number">12</span> 。</span><br><span class="line">机器人 <span class="number">2</span> 摘的樱桃数目为 (<span class="number">1</span> + <span class="number">5</span> + <span class="number">5</span> + <span class="number">1</span>) = <span class="number">12</span> 。</span><br><span class="line">樱桃总数为： <span class="number">12</span> + <span class="number">12</span> = <span class="number">24</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<p><img lazyload="" src="/images/loading.svg" data-src="https://i.loli.net/2020/11/10/aSykAceXPH1snjM.png"></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：grid = [[<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>],[<span class="number">2</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">0</span>],[<span class="number">2</span>,<span class="number">0</span>,<span class="number">9</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">3</span>,<span class="number">0</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">0</span>,<span class="number">0</span>],[<span class="number">1</span>,<span class="number">0</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">6</span>]]</span><br><span class="line">输出：<span class="number">28</span></span><br><span class="line">解释：机器人 <span class="number">1</span> 和机器人 <span class="number">2</span> 的路径在上图中分别用绿色和蓝色表示。</span><br><span class="line">机器人 <span class="number">1</span> 摘的樱桃数目为 (<span class="number">1</span> + <span class="number">9</span> + <span class="number">5</span> + <span class="number">2</span>) = <span class="number">17</span> 。</span><br><span class="line">机器人 <span class="number">2</span> 摘的樱桃数目为 (<span class="number">1</span> + <span class="number">3</span> + <span class="number">4</span> + <span class="number">3</span>) = <span class="number">11</span> 。</span><br><span class="line">樱桃总数为： <span class="number">17</span> + <span class="number">11</span> = <span class="number">28</span> 。</span><br></pre></td></tr></table></figure>
<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：grid = [[<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">3</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">3</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">3</span>],[<span class="number">9</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">3</span>]]</span><br><span class="line">输出：<span class="number">22</span></span><br></pre></td></tr></table></figure>
<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：grid = [[<span class="number">1</span>,<span class="number">1</span>],[<span class="number">1</span>,<span class="number">1</span>]]</span><br><span class="line">输出：<span class="number">4</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>rows == grid.length</li>
<li>cols == grid[i].length</li>
<li>2 &lt;= rows, cols &lt;= 70</li>
<li>0 &lt;= grid[i][j] &lt;= 100 </li>
</ul>
<h3 id="解法一-2"><a href="#解法一-2" class="headerlink" title="解法一"></a>解法一</h3><p>本来只写了前两题就打算push的，y总也只讲了这几道题，但是突然想起来很久之前的一道周赛题（27th双周赛T4），大概半年前了，没想到居然能想起来😄，看了下，和上面两题是一样的，随手写了下，一开始写的有bug，调试了好一会儿，最后把状态打出来手推了下，发现有些状态没有初始化好，导致递推的时候使用了非法的状态</p>
<p>先上暴力N^4的解法，这题范围不大，N^4勉强能扛过去</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//暴力N^4解法</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">cherryPickup2</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span> m = grid.length, n = grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">int</span>[][][][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[m+<span class="number">1</span>][n+<span class="number">2</span>][m+<span class="number">1</span>][n+<span class="number">2</span>];</span><br><span class="line">    <span class="keyword">int</span> INF = -<span class="number">0x3f3f3f3f</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i1 = <span class="number">0</span>; i1 &lt;= m; i1++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j1 = <span class="number">0</span>; j1 &lt;= n+<span class="number">1</span>; j1++) {</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i2 = <span class="number">0</span>; i2 &lt;= m; i2++) {</span><br><span class="line">                Arrays.fill(dp[i1][j1][i2], INF);</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    dp[<span class="number">1</span>][<span class="number">1</span>][<span class="number">1</span>][n] = grid[<span class="number">0</span>][<span class="number">0</span>]+grid[<span class="number">0</span>][n-<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i1 = <span class="number">2</span>; i1 &lt;= m; i1++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j1 = <span class="number">1</span>; j1 &lt;= n; j1++) {</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i2 = <span class="number">2</span>; i2 &lt;= m; i2++) {</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j2 = <span class="number">1</span>; j2 &lt;= n; j2++) {</span><br><span class="line">                    <span class="keyword">int</span> temp = INF;</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1][i2-<span class="number">1</span>][j2]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1][i2-<span class="number">1</span>][j2+<span class="number">1</span>]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1][i2-<span class="number">1</span>][j2-<span class="number">1</span>]);</span><br><span class="line">                    </span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1+<span class="number">1</span>][i2-<span class="number">1</span>][j2]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1+<span class="number">1</span>][i2-<span class="number">1</span>][j2+<span class="number">1</span>]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1+<span class="number">1</span>][i2-<span class="number">1</span>][j2-<span class="number">1</span>]);   </span><br><span class="line">                    </span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1-<span class="number">1</span>][i2-<span class="number">1</span>][j2]);</span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1-<span class="number">1</span>][i2-<span class="number">1</span>][j2+<span class="number">1</span>]);   </span><br><span class="line">                    temp = Math.max(temp, dp[i1-<span class="number">1</span>][j1-<span class="number">1</span>][i2-<span class="number">1</span>][j2-<span class="number">1</span>]);</span><br><span class="line">                    dp[i1][j1][i2][j2] = temp + ((i1==i2&amp;&amp;j1==j2) ? grid[i1-<span class="number">1</span>][j1-<span class="number">1</span>] : (grid[i1-<span class="number">1</span>][j1-<span class="number">1</span>] + grid[i2-<span class="number">1</span>][j2-<span class="number">1</span>]));</span><br><span class="line">                }</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j1 = <span class="number">0</span>; j1 &lt;= n; j1++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j2 = <span class="number">0</span>; j2 &lt;= n; j2++) {</span><br><span class="line">            res = Math.max(res, dp[m][j1][m][j2]);   </span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>

<h3 id="解法二-1"><a href="#解法二-1" class="headerlink" title="解法二"></a>解法二</h3><p>和上面两题一样，两个机器人走的层数是固定的，都是m层，所以可以优化掉一维的状态，同时上面的写法看起来也很ugly，可以用方向变量简化写法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//N^3解法，优化代码写法，简化代码</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">cherryPickup</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span>[] dir = {<span class="number">1</span>, -<span class="number">1</span>, <span class="number">0</span>};</span><br><span class="line">    <span class="keyword">int</span> m = grid.length, n = grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">//这题求最大值，在dp数组上边和左右两边各加一行作为边界</span></span><br><span class="line">    <span class="comment">//这里也可以用滚动数组优化下空间</span></span><br><span class="line">    <span class="keyword">int</span>[][][] dp = <span class="keyword">new</span> <span class="keyword">int</span>[m+<span class="number">1</span>][n+<span class="number">2</span>][n+<span class="number">2</span>];</span><br><span class="line">    <span class="keyword">int</span> INF = -<span class="number">0x3f3f3f3f</span>;</span><br><span class="line">    <span class="comment">//全部初始化为INF（实际上初始化两边和最上面的就ok了）</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> r = <span class="number">0</span>; r &lt;= m; r++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j1 = <span class="number">0</span>; j1 &lt;= n+<span class="number">1</span>; j1++) {</span><br><span class="line">            Arrays.fill(dp[r][j1], INF);</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    dp[<span class="number">1</span>][<span class="number">1</span>][n] = grid[<span class="number">0</span>][<span class="number">0</span>] + grid[<span class="number">0</span>][n-<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> r = <span class="number">2</span>; r &lt;= m; r++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j1 = <span class="number">1</span>; j1 &lt;= n; j1++) {</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j2 = <span class="number">1</span>; j2 &lt;= n; j2++) {</span><br><span class="line">                <span class="comment">//方向向量，简化写法</span></span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> d1 = <span class="number">0</span>; d1 &lt; <span class="number">3</span>; d1++) {</span><br><span class="line">                    <span class="keyword">for</span> (<span class="keyword">int</span> d2 = <span class="number">0</span>; d2 &lt; <span class="number">3</span>; d2++) {</span><br><span class="line">                        dp[r][j1][j2] = Math.max(dp[r][j1][j2], dp[r-<span class="number">1</span>][j1+dir[d1]][j2+dir[d2]]);</span><br><span class="line">                    }</span><br><span class="line">                }</span><br><span class="line">                dp[r][j1][j2] += (j1==j2 ? grid[r-<span class="number">1</span>][j1-<span class="number">1</span>] : (grid[r-<span class="number">1</span>][j1-<span class="number">1</span>] + grid[r-<span class="number">1</span>][j2-<span class="number">1</span>]));</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j1 = <span class="number">0</span>; j1 &lt;= n; j1++) {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j2 = <span class="number">0</span>; j2 &lt;= n; j2++) {</span><br><span class="line">            res = Math.max(res, dp[m][j1][j2]);   </span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：DP：数字三角形模型</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2020-11-09 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2020/11/09/22c967e1/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2020/11/14/f00d00a3/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">DP：最长上升子序列模型</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2020/09/04/ec7b18dc/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Fuck面试</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2020/11/09/22c967e1/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E5%AD%97%E4%B8%89%E8%A7%92%E5%BD%A2%E6%A8%A1%E5%9E%8B"><span class="nav-number">1.</span> <span class="nav-text">数字三角形模型</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1027-%E6%96%B9%E6%A0%BC%E5%8F%96%E6%95%B0"><span class="nav-number">2.</span> <span class="nav-text">1027. 方格取数</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%B8%80"><span class="nav-number">2.1.</span> <span class="nav-text">解法一</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%BA%8C"><span class="nav-number">2.2.</span> <span class="nav-text">解法二</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#275-%E4%BC%A0%E7%BA%B8%E6%9D%A1"><span class="nav-number">3.</span> <span class="nav-text">275. 传纸条</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%B8%80-1"><span class="nav-number">3.1.</span> <span class="nav-text">解法一</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1463-%E6%91%98%E6%A8%B1%E6%A1%83-II"><span class="nav-number">4.</span> <span class="nav-text">1463. 摘樱桃 II</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%B8%80-2"><span class="nav-number">4.1.</span> <span class="nav-text">解法一</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E6%B3%95%E4%BA%8C-1"><span class="nav-number">4.2.</span> <span class="nav-text">解法二</span></a></li></ol></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
